/*************************************************************************
 * File Name:    Partition_List.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 02 Nov 2013 02:21:48 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Partition List
 | Given a linked list and a value x, partition it such that all nodes
 | less than x come before nodes greater than or equal to x.
 |
 | You should preserve the original relative order of the nodes in each
 | of the two partitions.
 |
 | For example,
 | Given 1->4->3->2->5->2 and x = 3,
 | return 1->2->2->4->3->5.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *lhead, *ltail;
        ListNode *rhead, *rtail;
        
        lhead = rhead = NULL;
        ltail = rtail = NULL;
        for (ListNode *t = head; t != NULL; t = t->next) {
            if (t->val < x) {
                if (lhead == NULL) {
                    lhead = ltail = t;
                } else {
                    ltail->next = t;
                    ltail = t;
                }
            } else {
                if (rhead == NULL) {
                    rhead = rtail = t;
                } else {
                    rtail->next = t;
                    rtail = t;
                }
            }
        }
        if (lhead == NULL) lhead = rhead;
        else ltail->next = rhead;
        
        if (rtail != NULL) rtail->next = NULL;

        return lhead;
    }
};
;


int
main(int argc, char *argv[])
{
    ListNode *head = new ListNode(2);
    head->next = new ListNode(1);
    head->next->next = NULL;

    Solution sol;
    head = sol.partition(head, 2);
    while (head != NULL) {
        cout << head->val << endl;
        head = head->next;
    }

    return 0;
}
